package com.duoduo.剑指Offer;

import com.duoduo.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @program: algorithm
 * @description: 二叉树中和为某一值的路径31
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 *
 * @author: chaidl  ！
 * @create: 2022-05-26 21:38
 */
public class 二叉树中和为某一值的路径31 {
	LinkedList<List<Integer>> result = new LinkedList<>();
	LinkedList<Integer> list = new LinkedList<>();
	public List<List<Integer>> pathSum(TreeNode root, int target) {
		dfs(root,target);
		return result;
	}
	private void dfs(TreeNode root, int target) {
		if (root==null){
			return;
		}
		//从根节点开始依次将数字加入lsit
		list.add(root.val );
		//每次target都减去当前的值
		target-=root.val;
		//当当前的root左右节点都为空，并且target==0说明是符合满足条件的
		if (target==0 && root.left==null && root.right == null){
			result.add(new LinkedList<>(list));
		}
		dfs(root.left,target);
		dfs(root.right, target);
		list.removeLast();
	}
}
